package com.github.hgkmail.hello.leetcode101.top100;

import java.util.Arrays;

public class LC16ThreeSumClosest {
    //排序，然后固定一个指针，移动2个指针
    public int threeSumClosest(int[] nums, int target) {
        //base case
        int n=nums.length;
        if (n<=0) {
            return 0;
        }
        if (n<=3) {
            return Arrays.stream(nums).sum();
        }
        Arrays.sort(nums);
        int k=0, i, j;
        int res=0, resDiff=Integer.MAX_VALUE;
        int sum, diff;
        while (k<n-2) {
            i=k+1;
            j=n-1;
            while (i<j) {
                sum = nums[k]+nums[i]+nums[j];
                diff = Math.abs(target-sum);
                if (diff < resDiff) {
                    res=sum;
                    resDiff=diff;
                }
                if (target-sum==0) {
                    return res;
                } else if (target>sum) {
                    i++;
                } else {
                    j--;
                }
            }
            k++;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LC16ThreeSumClosest().threeSumClosest(new int[]{-1,2,1,-4}, 1));
    }
}
